package com.newcode;


import java.util.*;

/**
 * @Author: huangzhigao
 * @Date: 2022/2/26 14:21
 */
public class BM1 {

    public static class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode ReverseList(ListNode head) {
        if (head == null) {
            return null;
        }


        ListNode pre = null;
        while (head != null) {
            ListNode cur = head.next;
            head.next = pre;
            pre = head;
            head = cur;
        }

        return pre;
    }


    public ListNode reverseBetween(ListNode head, int m, int n) {
        ArrayList<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }

        Object[] objects = list.toArray();
        while (m < n) {
            Object tmp = objects[m - 1];
            objects[m - 1] = objects[n - 1];
            objects[n - 1] = tmp;
            m++;
            n--;
        }

        ListNode res = null;
        ListNode tail = null;
        for (Object o : objects) {
            if (res == null) {
                res = tail = new ListNode((int) o);
            } else {
                tail.next = new ListNode((int) o);
                tail = tail.next;
            }
        }
        return res;
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        LinkedList<Integer> queue = new LinkedList<>();

        ListNode res = null;
        ListNode tail = null;
        while (head != null) {
            queue.add(head.val);
            head = head.next;
            if (queue.size() == k) {
                while (!queue.isEmpty()) {
                    if (res == null) {
                        res = tail = new ListNode(queue.pollLast());
                    } else {
                        tail.next = new ListNode(queue.pollLast());
                        tail = tail.next;
                    }
                }
            }
        }


        while (!queue.isEmpty()) {
            if (res == null) {
                res = tail = new ListNode(queue.pop());
            } else {
                tail.next = new ListNode(queue.pop());
                tail = tail.next;
            }
        }
        return res;
    }


    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        Queue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });

        for (ListNode node : lists) {
            queue.add(node);
        }

        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (!queue.isEmpty()) {
            ListNode poll = queue.poll();
            cur.next = poll;
            cur = cur.next;
            if (poll.next != null) {
                queue.add(poll.next);
            }
        }
        return dummy.next;
    }


    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return true;
        }

        Set<ListNode> map = new HashSet<>();
        while (head != null) {
            if (map.contains(head)) {
                return false;
            }
            map.add(head);
            head = head.next;
        }
        return true;

    }


    public boolean hasCycle2(ListNode head) {
        if (head == null) {
            return false;
        }

        ListNode fast = head;
        ListNode slow = head;

        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;

    }


    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode tail = new ListNode(2);
        head.next = tail;
        reverseKGroup(head, 2);
    }
}
